package gold.digger;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC802 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * 带染色的dfs，需要学习人家的思想啊！
     * @return:
     */
    class Solution {
        public List<Integer> eventualSafeNodes(int[][] graph) {
            int N = graph.length;
            int[] color = new int[N];
            List<Integer> ans = new ArrayList();

            for (int i = 0; i < N; ++i)
                if (dfs(i, color, graph))
                    ans.add(i);
            return ans;
        }

        // colors: WHITE 0, GRAY 1, BLACK 2;
        public boolean dfs(int node, int[] color, int[][] graph) {
            if (color[node] > 0)
                return color[node] == 2;

            color[node] = 1;
            for (int nei : graph[node]) {
                if (color[node] == 2)
                    continue;
                if (color[nei] == 1 || !dfs(nei, color, graph))
                    return false;
            }

            color[node] = 2;
            return true;
        }
    }

    class Solution_Time_exceeed {
        public int n = 0;

        public List<Integer> eventualSafeNodes(int[][] graph) {
            n = graph.length - 1;
            Set<Integer> curPath = new LinkedHashSet<>();
            Set<Integer> repeat = new LinkedHashSet<>();
            for (int i = 0; i <= n; i++) {
                if (repeat.contains(i)) continue;
                dfs(graph, i, curPath, repeat);
            }

            List<Integer> res = new ArrayList<Integer>();
            for (int i = 0; i <= n; i++) {
                if (!repeat.contains(i)) res.add(i);
            }
            return res;
        }

        public void dfs(int[][] graph, int cur, Set<Integer> curPath, Set<Integer> repeat) {
            if (curPath.contains(cur)) {
                repeat.addAll(curPath);
                return;
            }

            curPath.add(cur);
            for (int next : graph[cur]) {
                if (repeat.contains(next)) {
                    repeat.addAll(curPath);
                    curPath.remove(cur);
                    return;
                }
                dfs(graph, next, curPath, repeat);
            }
            curPath.remove(cur);
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[][] arr = {{21, 52, 85, 128, 163, 194}, {50, 71, 105, 116, 159, 174}, {}, {28, 126, 134}, {33}, {21, 42, 101, 107}, {55, 139}, {71}, {108, 109, 112, 129}, {34, 42, 51, 54, 132, 165}, {29, 106}, {74, 101, 125, 171, 197}, {57, 124, 138, 139, 158}, {134, 140}, {47, 82, 116, 134, 156}, {}, {166}, {}, {41}, {106, 183}, {73, 77, 101, 140, 153, 181}, {34, 59, 67, 158}, {58, 64, 97, 107, 159, 174}, {52, 127}, {6}, {130, 149, 196}, {0, 30, 76}, {76, 129, 139, 188}, {80}, {}, {34, 108, 140, 146, 155, 167}, {132, 139}, {}, {120, 126, 134, 166}, {67}, {40, 55, 115, 137, 182, 187}, {52, 76, 94, 145, 157}, {42, 60, 104}, {55, 78, 88, 166, 175}, {}, {46, 52, 69, 121, 123}, {184}, {60, 65, 79, 157}, {66, 149, 151, 176, 198}, {160}, {}, {140}, {96, 154, 191}, {49, 63, 139}, {88, 127, 166, 176, 198}, {23, 78, 96, 119, 152, 167, 177}, {119}, {86, 147, 196}, {99, 109, 157, 185, 187}, {71, 93, 138, 158, 161, 197}, {66, 72, 107, 133, 136, 150}, {79, 89, 158}, {139, 151}, {85, 91, 118, 142, 173, 185}, {104, 118}, {66, 84, 102, 110, 171}, {}, {146, 172, 186}, {}, {101, 126}, {161, 178, 190}, {77, 113, 152, 184}, {60}, {82, 124, 129, 138, 174, 185}, {156}, {82, 87, 88, 128, 191}, {144, 164, 165, 175, 190}, {105, 117, 141, 152, 157, 172}, {109, 118, 172, 188}, {84, 150, 153, 168}, {162}, {}, {117, 120}, {104, 165}, {138}, {88, 132, 153, 169, 183, 193}, {87, 121, 134, 135, 150, 159}, {40}, {123}, {160}, {89, 108, 161, 170, 185}, {88, 116, 155, 156, 160}, {98, 106, 155, 162, 173}, {96, 125, 186}, {102, 128, 155, 179}, {93, 95, 175, 180, 192}, {}, {97, 117, 133, 159, 186}, {96, 123, 144, 165, 189}, {30, 111}, {80, 131}, {}, {105, 136, 150, 179, 186}, {123, 149, 161, 175}, {142, 166}, {142, 180, 189}, {133, 161, 168, 183, 196}, {108, 110, 121, 136, 143, 198}, {112, 116, 127, 133, 142, 195}, {115, 185, 196}, {118, 141, 154, 164, 184, 199}, {108, 127, 153, 170, 190}, {116, 152}, {96, 170, 171}, {}, {115, 128, 169, 172, 191, 195}, {121, 146, 170, 184}, {116, 140, 148, 155, 179, 180}, {108, 114, 153, 161, 182, 196}, {131, 164, 172, 177, 180, 187}, {176, 193}, {84, 152, 154, 186}, {152, 177, 194}, {136, 137, 148, 157, 166}, {157, 168, 182, 184}, {}, {128, 155, 158, 190}, {148, 161}, {171}, {152, 164, 173}, {128, 140, 141, 165}, {143, 145, 177, 183}, {}, {136, 149, 177, 183, 184, 190}, {}, {5}, {133, 167, 185}, {100, 180, 187, 189}, {149, 153, 199}, {}, {}, {143, 166, 180, 182, 197, 198}, {}, {}, {157, 158, 170, 186}, {148, 170, 174}, {152}, {168}, {144, 168, 175, 190, 197}, {166, 178, 179}, {179, 187}, {147, 157, 184}, {160, 165}, {172, 175, 183}, {159}, {}, {190}, {153, 163, 193}, {39, 162, 164, 191}, {159, 164, 177, 178, 192}, {162, 177, 191, 193, 194, 196}, {165, 168, 178, 181}, {161, 163, 166, 175, 193, 197}, {159, 161, 175, 178, 180, 182}, {160, 166, 176, 184, 185, 192}, {161, 178, 182, 184, 195, 196}, {172, 197}, {170, 179, 186, 188, 191, 198}, {}, {171, 180, 182, 195}, {175, 189, 191}, {172, 178, 181, 189, 193, 195}, {169, 171, 178, 179, 194}, {188}, {170, 191, 198}, {173, 182, 199}, {178, 186, 198}, {}, {186, 188, 193, 194}, {179}, {184, 185, 187, 190, 198, 199}, {181, 184, 190, 194}, {}, {181, 182, 188, 190, 192, 197}, {182, 189, 195, 199}, {188, 192, 199}, {167, 190}, {184, 191, 196, 197, 199}, {186, 188, 193, 197}, {185, 190, 191, 199}, {194}, {187, 188, 189, 193, 199}, {195, 196, 198}, {197, 198, 199}, {196, 197, 198}, {191, 192, 193, 195, 197, 199}, {4, 192, 194}, {}, {195, 199}, {195, 196, 197, 198, 199}, {196}, {}, {198, 199}, {199}, {}};
        System.out.println(solution.eventualSafeNodes(arr));
    }

    public static void main(String[] args) throws Exception {
        LC802 an = new LC802();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
